import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2024-07-20
 * Time:23:26
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
public class TSort {
    //冒泡
    public void bubble(int[] arr){
        for(int i = 0;i<arr.length-1;i++){
            int flg = 1;
            for(int j = 0;j< arr.length-i-1;j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flg = 0;
                }
            }
            if(flg == 1){
                break;
            }
        }
    }
    //选择
    public void select(int[] arr){
        for(int i = 0;i<arr.length;i++){
            int min = i;
            for(int j = i+1;j<arr.length;j++){
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    //希尔
    public void shell(int[] arr){
        for(int add = arr.length/2;add > 0;add /= 2){
            for(int i = add;i<arr.length;i++){
                int insert = arr[i];
                int j = i - add;
                while (j >= 0 && insert < arr[j]){
                    arr[j + add] = arr[j];
                    j-=add;
                }
                arr[j + add] = insert;
            }
        }
    }
    //插入
    public void insert(int[] arr){
        for(int i = 1;i<arr.length;i++){
            int j = i - 1;
            int insert = arr[i];
            while (j >= 0 && insert < arr[j]){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = insert;
        }
    }
    //快速
    public void quick(int[] arr,int left, int right){
        if(left >= right){
            return;
        }
        //基准
        int base = arr[left];
        int i = left;
        int j = right;
        while (i < j){
            while (i < j && arr[j] >= base){
                j--;
            }
            while (i < j && arr[i] <= base){
                i++;
            }
            if(i < j){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        arr[left] = arr[i];
        arr[i] = base;
        //左
        quick(arr, left, i-1);
        //右
        quick(arr,i+1,right);
    }
    //归并
    public void merge(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        //分
        int mid = (left + right)/2;
        merge(arr,left,mid);
        merge(arr,mid+1,right);
        //和
        mergeSort(arr, left, mid, right);
    }
    public void mergeSort(int[] arr, int left, int mid, int right){
        int i = left;
        int j = mid+1;
        int[] tmp = new int[right-left+1];
        int k = 0;
        while (i <= mid && j <= right){
            if(arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        while (i <= mid){
            tmp[k++] = arr[i++];
        }
        while (j <= right){
            tmp[k++] = arr[j++];
        }

        int Tleft = left;
        for(int index = 0;index<tmp.length;index++){
            arr[Tleft++] = tmp[index];
        }
    }
    //堆
    public void heap(int[] arr){
        //构建一个大根堆
        for(int i = (arr.length-1)/2;i>=0;i--){
            Adjust(arr, i, arr.length);
        }

        for(int i = arr.length-1;i>0;i--){
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            Adjust(arr,0,i);
        }
    }
    public void Adjust(int[] arr,int index, int len){
        int tmp = arr[index];
        for(int k = 2 * index+1;k<len;k=2*k+1){
            if(k+1 < len && arr[k+1] > arr[k]){
                k++;
            }
            if(tmp < arr[k]){
                arr[index] = arr[k];
                index = k;
            } else {
                break;
            }
        }
        arr[index] = tmp;
    }
    //计数
    public void number(int[] arr){

    }
    public static void main(String[] args) {
//        int[] arr = {3,5,1,8,0,7,5,4,6,8,2,9};
        TSort sort = new TSort();
//        sort.bubble(arr);
//        sort.insert(arr);
//        sort.quick(arr,0,arr.length-1);
//        sort.merge(arr,0, arr.length-1);
//        sort.heap(arr);
        int[] arr = {1,2,3,4,5,6,7,8,9};
        TreeNode ret = test(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static TreeNode test(int[] arr) {
        if(arr == null || arr.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(arr[arr.length/2]);
        if(arr.length == 1){
            return root;
        }
        root.left = test(Arrays.copyOfRange(arr,0,arr.length/2));
        root.right = test(Arrays.copyOfRange(arr,arr.length/2+1,arr.length));
        return root;
    }
}
